{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEICAYAAACktLTqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFOhJREFUeJzt3X+w3XV95/HnCxLtGgJYknUJP0wrsf5oxR+x0jG70nan\nArp12tFGdGFhUXTXqbi6rrvuWNzRdnWs1roUMVWaOnVoWmUrWnSxs2qWRbAXhh9CHEmxQCCaK4gm\noXWNee8f3y9yvNwfJ7nn3Jv7yfMxc+eecz6f+/m8P+ckr/O9n/O956SqkCS15YjFLkCSNHqGuyQ1\nyHCXpAYZ7pLUIMNdkhpkuEtSgwz3w1ySzUnePc8xXp3kmiH6XZbkHfOZSwcnydoklWTZYteihWG4\na96q6hNV9WtD9Ht9Vb1rIWqCQy/QkrwzyZ+NaKxKcsooxppm7NOT7BjH2Fo4hrskNchwP8wkeU6S\nm5LsTrIF+Kkp7S9NcnOSh5Jcl+RZA20nJbkyyWSSB5Jc0t9+XpJr+8tJ8gdJdiX5fpLbkvx83/YT\nW0BJXptke5IHk1yVZM1AWyV5fZI7+1r+KElmWNMvJpno5/t2kg/0TVv77w8l2ZPkl6YePU89uk/y\npSTv7te+J8lnkhyX5BP9+H+bZO2UOt+Y5K4k30nyviSP+X+V5Azg7cDGftxb+tuPSfKxJDuT3NfP\nfWTfdkqSLyf5Xj/2lv72R9Z1Sz/WxmnmOzLJ7/c/dxfwkint5yfZ1v87uCvJ6/rbVwCfA9b0Y+9J\nsqa/j7/SPxY7k1yS5HHTPR46RFSVX4fJF/A44G7gPwDLgZcDPwTe3bc/B9gFvAA4Evg3wN8Dj++v\n3wL8AbCC7klhQ/9z5wHX9pdfDNwIHAsEeDpwfN+2eWCuXwG+Azy3H/9/AFsHai3gs/04JwOTwBkz\nrOsrwDn95aOA0/rLa/txlg30fSfwZwPXf6IP8CVgO/AU4BjgDuAbwL8ElgEfB/5kSp1fBH66r/Mb\nwGtmqPMn5u5v+5/AR/r79J8CXwVe17ddAfxXuoOwH9/fA/OeMstj/Xrg68BJfW1fnLLOl/RrDPAi\n4GHguX3b6cCOKeM9Dzitvw/WAtuANy32v2m/Zv7yyP3wchpdqH+wqn5YVZ8E/nag/ULgI1V1Q1X9\nqKr+FPhB/3O/CKwB3lpVe6vqH6vq2mnm+CGwEngakKraVlU7p+n3auDyqrqpqn4A/BfglwaPioH3\nVNVDVXUPXTg9e4Z1/RA4JcmqqtpTVdcPdW/M7E+q6u+q6nt0R7F/V1V/U1X7gL+kexIc9N6qerCv\n84PA2cNMkuRJwFl0Ibm3qnbRPXm+cmBdTwbWzHJ/z+S36B7ne6vqQeC/DzZW1V/3a6yq+jJwDfDP\nZxqsqm6squural9V/T3dE9KLDqAeLTDD/fCyBrivqgbfLe7ugctPBt7S/+r9UJKH6I781vTf7+4D\nbkZV9b+BS4A/AnYl2ZTk6BlquXvg5/YADwAnDPT51sDlh+mOyqdzAfBU4Ov9tslLZ6txCN8euPwP\n01yfWse9A5fvplvbMJ5M92S7c+D+/gjdETzAf6I7sv5qktuT/Nshx6WvYWpdP5bkzCTX91tiD9E9\nyayaabAkT03y2STfSvJ94Pdm66/FZ7gfXnYCJ0zZuz554PK9wO9W1bEDX0+oqiv6tpMzxJknVfWh\nqnoe8Ay60H3rNN3upws34Md7vccB9x3ooqrqzqo6my4U3wt8sh9vurc83Qs8YeD6PzvQ+aZx0sDl\nk+nWNm2pU67fS/eb0aqB+/voqnomQFV9q6peW1VrgNcBl2b4M2R2TlMXAEkeD3wK+H3gSVV1LHA1\n3RPJdHUCfJhum2ddVR1N9/rBtK+B6NBguB9evgLsA96YZHmS36TbbnnEHwOvT/KC/oXRFUlekmQl\n3V7wTuA9/e0/leSFUydI8vz+55fTBek/AvunqeUK4Pwkz+7D5veAG/pf+Q9Ikn+dZHVV7Qce6m/e\nT7dPvx/42YHuNwP/IsnJSY6h2w6ar7cmeWKSk4CLgC0z9Ps2sPaRF1z77aprgPcnOTrJEUmekuRF\n/bpekeTE/me/Sxe6+wfG+llm9hd0j/OJSZ4I/OeBtsfRvc4xCexLciYweCrrt4Hj+vvnESuB7wN7\nkjwN+HezzK1DgOF+GKmq/wf8Jt0LoA8CG4ErB9ongNfSbat8l+6FxfP6th8B/wo4BbgH2NH//FRH\n0z1JfJduK+AB4H3T1PI3wDvojiB30r2498qp/YZ0BnB7kj3AHwKvrKp/qKqHgd8F/m+/7XFaVX2B\nLnxvpXvh97MHOeegT/dj3Qz8NfCxGfr9Zf/9gSQ39ZfPpQvbO+jus08Cx/dtzwdu6Nd1FXBRVd3V\nt70T+NN+Xb81zVx/DPwvuhfBb+InH+fdwBvpngC+C7yqH/+R9q/TPfne1Y+/BviPfb/d/dgzPYHp\nEJGf3H6VdCCSFN1WxfbFrkUa5JG7JDXIcJekBrktI0kN8shdkhq0aO+Wt2rVqlq7du1iTS9JS9KN\nN974napaPVe/RQv3tWvXMjExsVjTS9KSlOTuuXu5LSNJTTLcJalBhrskNchwl6QGHRKfLTkvu3fD\nli1w552wbh1s3AgrVy52VZK0qJZ2uF97LZx1FuzfD3v3wooV8OY3w9VXw4YNi12dJC2apbsts3t3\nF+y7d3fBDt33R27fs2dx65OkRbR0w33Llu6IfTr793ftknSYWrrhfuedjx6xT7V3L2z3HVglHb6W\nbrivW9ftsU9nxQo4ZdhPI5Ok9izdcN+4EY6YofwjjujaJekwtXTDfeXK7qyYlSsfPYJfseLR24+a\n+gH1knT4WNqnQm7YAPff3714un17txWzcaPBLumwt7TDHbogv+CCxa5Ckg4pS3dbRpI0I8Ndkhpk\nuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1KA5wz3JSUm+mOSOJLcnuWiaPknyoSTbk9ya\n5LnjKVeSNIxh3n5gH/CWqropyUrgxiRfqKo7BvqcCazrv14AfLj/LklaBHMeuVfVzqq6qb+8G9gG\nnDCl28uAj1fneuDYJMePvFpJ0lAOaM89yVrgOcANU5pOAO4duL6Dxz4BkOTCJBNJJiYnJw+sUknS\n0IYO9yRHAZ8C3lRV3z+YyapqU1Wtr6r1q1evPpghJElDGCrckyynC/ZPVNWV03S5Dzhp4PqJ/W2S\npEUwzNkyAT4GbKuqD8zQ7Srg3P6smdOA71XVzhHWKUk6AMOcLfNC4BzgtiQ397e9HTgZoKouA64G\nzgK2Aw8D54++VEnSsOYM96q6FsgcfQp4w6iKkiTNj3+hKkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNd\nkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWp\nQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUFzhnuSy5PsSvK1GdqPSfKZJLck\nuT3J+aMvU5J0IIY5ct8MnDFL+xuAO6rqVOB04P1JHjf/0iRJB2vOcK+qrcCDs3UBViYJcFTfd99o\nypMkHYxR7LlfAjwduB+4DbioqvZP1zHJhUkmkkxMTk6OYGpJ0nRGEe4vBm4G1gDPBi5JcvR0Hatq\nU1Wtr6r1q1evHsHUkqTpjCLczweurM524JvA00YwriTpII0i3O8BfhUgyZOAnwPuGsG4kqSDtGyu\nDkmuoDsLZlWSHcDFwHKAqroMeBewOcltQIC3VdV3xlaxJGlOc4Z7VZ09R/v9wK+NrCJJ0rz5F6qS\n1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkN\nMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDD\nXZIaNGe4J7k8ya4kX5ulz+lJbk5ye5Ivj7ZESdKBGubIfTNwxkyNSY4FLgV+vaqeCbxiNKVJkg7W\nnOFeVVuBB2fp8irgyqq6p++/a0S1SZIO0ij23J8KPDHJl5LcmOTcmTomuTDJRJKJycnJEUwtSZrO\nKMJ9GfA84CXAi4F3JHnqdB2ralNVra+q9atXrx7B1JKk6SwbwRg7gAeqai+wN8lW4FTgGyMYW5J0\nEEZx5P5pYEOSZUmeALwA2DaCcSVJB2nOI/ckVwCnA6uS7AAuBpYDVNVlVbUtyeeBW4H9wEerasbT\nJiVJ4zdnuFfV2UP0eR/wvpFUJEmaN/9CVZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnu\nktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5J\nDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoPmDPcklyfZleRrc/R7fpJ9SV4+uvIkSQdjmCP3\nzcAZs3VIciTwXuCaEdQkSZqnOcO9qrYCD87R7beBTwG7RlGUJGl+5r3nnuQE4DeAD8+/HEnSKIzi\nBdUPAm+rqv1zdUxyYZKJJBOTk5MjmFqSNJ1lIxhjPfDnSQBWAWcl2VdVfzW1Y1VtAjYBrF+/vkYw\ntyRpGvMO96r6mUcuJ9kMfHa6YJckLZw5wz3JFcDpwKokO4CLgeUAVXXZWKuTJB2UOcO9qs4edrCq\nOm9e1UiSRsK/UJWkBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNd\nkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWp\nQYa7JDXIcJekBhnuktQgw12SGjRnuCe5PMmuJF+bof3VSW5NcluS65KcOvoyJUkHYpgj983AGbO0\nfxN4UVX9AvAuYNMI6pIkzcOyuTpU1dYka2dpv27g6vXAifMvS5I0H6Pec78A+NxMjUkuTDKRZGJy\ncnLEU0uSHjGycE/yy3Th/raZ+lTVpqpaX1XrV69ePaqpJUlTzLktM4wkzwI+CpxZVQ+MYkxJ0sGb\n95F7kpOBK4Fzquob8y9JkjRfcx65J7kCOB1YlWQHcDGwHKCqLgN+BzgOuDQJwL6qWj+ugiVJcxvm\nbJmz52h/DfCakVUkSZo3/0JVkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGjeTtByRJc9i9\nG7ZsgTvvhHXrYONGWLlybNMZ7pI0btdeC2edBfv3w969sGIFvPnNcPXVsGHDWKZ0W0aSxmn37i7Y\nd+/ugh2674/cvmfPWKY13CVpnLZs6Y7Yp7N/f9c+Boa7JI3TnXc+esQ+1d69sH37WKY13CVpnNat\n6/bYp7NiBZxyylimNdwlaZw2boQjZojaI47o2sfAcJekcVq5sjsrZuXKR4/gV6x49PajjhrLtJ4K\nKUnjtmED3H9/9+Lp9u3dVszGjWMLdjDcJWlhHHUUXHDBgk3ntowkNchwl6QGGe6S1CDDXZIaZLhL\nUoMMd0lqkOEuSQ1akue5P/Piz7P3Bz+as9+Kxx/J7f/tjAWoqD3ex9LStiTDfZjQOZB+eizvY2nE\nDrVPYkpyOfBSYFdV/fw07QH+EDgLeBg4r6puGnWhkrRkHaKfxLQZmO337jOBdf3XhcCH51+WJDXi\nUP0kpqraCjw4S5eXAR+vzvXAsUmOH1WBkrSkLeFPYjoBuHfg+o7+tsdIcmGSiSQTk5OTI5hakg5x\nh8MnMVXVpqpaX1XrV69evZBTS9LiWMKfxHQfcNLA9RP72yRJS/iTmK4Czk3nNOB7VbVzBONK0tJ3\nqH4SU5IrgNOBVUl2ABcDywGq6jLgarrTILfTnQp5/lgqlaSl6lD8JKaqOnuO9gLeMLKKhrDi8UcO\n/deTOjjex9KILfAnMaXL5oW3fv36mpiYWJS5JWmpSnJjVa2fq59vHCZJDTLcJalBhrskNchwl6QG\nGe6S1CDDXZIaZLhLUoMW7Tz3JJPA3SMcchXwnRGOdyg7nNYKrrd1rvfAPLmq5nznxUUL91FLMjHM\nif0tOJzWCq63da53PNyWkaQGGe6S1KCWwn3TYhewgA6ntYLrbZ3rHYNm9twlSY9q6chdktQz3CWp\nQUsq3JNcnmRXkq/N0J4kH0qyPcmtSZ670DWO0hDrfXW/ztuSXJfk1IWucVTmWutAv+cn2Zfk5QtV\n2zgMs94kpye5OcntSb68kPWN2hD/lo9J8pkkt/TrXbKf6JbkpCRfTHJHv5aLpukz9qxaUuEObAbO\nmKX9TGBd/3Uh8OEFqGmcNjP7er8JvKiqfgF4F0v7hanNzL5WkhwJvBe4ZiEKGrPNzLLeJMcClwK/\nXlXPBF6xQHWNy2Zmf3zfANxRVafSfazn+5M8bgHqGod9wFuq6hnAacAbkjxjSp+xZ9WSCveq2go8\nOEuXlwEfr871wLFJjl+Y6kZvrvVW1XVV9d3+6vXAiQtS2BgM8dgC/DbwKWDX+CsaryHW+yrgyqq6\np++/pNc8xHoLWJkkwFF9330LUduoVdXOqrqpv7wb2AacMKXb2LNqSYX7EE4A7h24voPH3qmtugD4\n3GIXMS5JTgB+g6X/29iwngo8McmXktyY5NzFLmjMLgGeDtwP3AZcVFX7F7ek+UuyFngOcMOUprFn\n1ZwfkK1DX5Jfpgv3DYtdyxh9EHhbVe3vDu6atwx4HvCrwD8BvpLk+qr6xuKWNTYvBm4GfgV4CvCF\nJP+nqr6/uGUdvCRH0f2m+abFWEdr4X4fcNLA9RP725qV5FnAR4Ezq+qBxa5njNYDf94H+yrgrCT7\nquqvFressdkBPFBVe4G9SbYCpwKthvv5wHuq+8Ob7Um+CTwN+OrilnVwkiynC/ZPVNWV03QZe1a1\nti1zFXBu/0r0acD3qmrnYhc1LklOBq4Ezmn4iA6AqvqZqlpbVWuBTwL/vuFgB/g0sCHJsiRPAF5A\nt3fbqnvofkshyZOAnwPuWtSKDlL/usHHgG1V9YEZuo09q5bUkXuSK+heSV+VZAdwMbAcoKouA64G\nzgK2Aw/THQ0sWUOs93eA44BL+yPafUv13fWGWGtT5lpvVW1L8nngVmA/8NGqmvU00UPZEI/vu4DN\nSW4DQrcFt1TfBviFwDnAbUlu7m97O3AyLFxW+fYDktSg1rZlJEkY7pLUJMNdkhpkuEtSgwx3SWqQ\n4S5JDTLcJalB/x+HHGZYb8WFmAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x62bd5f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#adaptive boosting:是一种集成方法，通过组合多个弱分类器的分类结果，进行加权求和的分类结果\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def loadSimpData():\n",
    "    datMat = np.matrix(\n",
    "        [[ 1. ,  2.1],\n",
    "        [ 2. ,  1.1],\n",
    "        [ 1.3,  1. ],\n",
    "        [ 1. ,  1. ],\n",
    "        [ 2. ,  1. ]])\n",
    "    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]\n",
    "    return datMat,classLabels\n",
    "\n",
    "datMat,classLabels = loadSimpData()\n",
    "\n",
    "#绘制一下\n",
    "\n",
    "xcord0 = []\n",
    "ycord0 = []\n",
    "xcord1 = []\n",
    "ycord1 = []\n",
    "markers =[]\n",
    "colors =[]\n",
    "\n",
    "for i in range(len(classLabels)):\n",
    "    if classLabels[i]==1.0:\n",
    "        xcord1.append(datMat[i,0]), ycord1.append(datMat[i,1])\n",
    "    else:\n",
    "        xcord0.append(datMat[i,0]), ycord0.append(datMat[i,1])\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111)       \n",
    "ax.scatter(xcord0,ycord0, marker='s', s=90)\n",
    "ax.scatter(xcord1,ycord1, marker='o', s=50, c='red')\n",
    "plt.title('decision stump test data')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#分类函数\n",
    "#(数据集，特征，阈值，阈值判定方法)\n",
    "def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data\n",
    "    retArray = np.ones((np.shape(dataMatrix)[0],1)) #这里分为1和-1两个类别\n",
    "    if threshIneq == 'lt':\n",
    "        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0\n",
    "    else:\n",
    "        retArray[dataMatrix[:,dimen] > threshVal] = -1.0\n",
    "    return retArray\n",
    "    \n",
    "#构建单层决策树（decision stump决策树桩）\n",
    "#(数据集，分类标签y,样本数据的权重向量D)\n",
    "def buildStump(dataArr,classLabels,D):\n",
    "    dataMatrix = np.mat(dataArr)\n",
    "    labelMat = np.mat(classLabels).T\n",
    "    m,n = np.shape(dataMatrix)\n",
    "    numSteps = 10.0\n",
    "    bestStump = {}\n",
    "    bestClasEst = np.mat(np.zeros((m,1)))\n",
    "    minError = np.inf #init error sum, to +infinity\n",
    "    for i in range(n):#loop over all dimensions遍历所有特征\n",
    "        rangeMin = dataMatrix[:,i].min()\n",
    "        rangeMax = dataMatrix[:,i].max()\n",
    "        stepSize = (rangeMax-rangeMin)/numSteps #针对连续数值型的特征，通过步长来选择合适的分界值\n",
    "        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension\n",
    "            for inequal in ['lt', 'gt']: #go over less than and greater than切换大于和小于的判断\n",
    "                threshVal = (rangeMin + float(j) * stepSize) #可以看到，j=11，会超出范围\n",
    "                #这里调用预测分类函数\n",
    "                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan\n",
    "                errArr = np.mat(np.ones((m,1)))\n",
    "                errArr[predictedVals == labelMat] = 0\n",
    "                weightedError = D.T*errArr  #calc total error multiplied by D加权错误率\n",
    "                #print \"split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f\" % (i, threshVal, inequal, weightedError)\n",
    "                if weightedError < minError: #选择最佳的单层决策树，最小的加权错误率（而不是错误率）\n",
    "                    minError = weightedError\n",
    "                    bestClasEst = predictedVals.copy()\n",
    "                    bestStump['dim'] = i\n",
    "                    bestStump['thresh'] = threshVal\n",
    "                    bestStump['ineq'] = inequal\n",
    "    return bestStump,minError,bestClasEst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 0, thresh 1.00, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 0, thresh 1.10, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 0, thresh 1.10, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 0, thresh 1.20, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 0, thresh 1.20, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 0, thresh 1.30, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.30, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.40, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.40, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.50, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.50, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.60, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.60, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.70, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.70, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.80, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.80, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 1.90, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 0, thresh 1.90, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 0, thresh 2.00, thresh ineqal: lt, the weighted error is 0.600\nsplit: dim 0, thresh 2.00, thresh ineqal: gt, the weighted error is 0.400\nsplit: dim 1, thresh 0.89, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 0.89, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.00, thresh ineqal: lt, the weighted error is 0.200\nsplit: dim 1, thresh 1.00, thresh ineqal: gt, the weighted error is 0.800\nsplit: dim 1, thresh 1.11, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.11, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.22, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.22, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.33, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.33, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.44, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.44, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.55, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.55, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.66, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.66, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.77, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.77, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.88, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.88, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 1.99, thresh ineqal: lt, the weighted error is 0.400\nsplit: dim 1, thresh 1.99, thresh ineqal: gt, the weighted error is 0.600\nsplit: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.600\nsplit: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.400\n"
     ]
    }
   ],
   "source": [
    "D = np.mat(np.ones((5,1)) / 5.0) #所有向量之和=1\n",
    "bestStump,minError,bestClasEst = buildStump(datMat,classLabels,D)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'dim': 0, 'ineq': 'lt', 'thresh': 1.3}\n[[ 0.2]]\n[[-1.]\n [ 1.]\n [-1.]\n [-1.]\n [ 1.]]\n"
     ]
    }
   ],
   "source": [
    "print bestStump\n",
    "print minError\n",
    "print bestClasEst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "#单层决策树的训练过程 ：p117的公式\n",
    "#首先，基于样本的权重向量D（开始每个样本都是相同值）,\n",
    "# 然后训练一个弱分类器（单层决策树），并且得到分类的错误率（加权）和该分类器的权重值alpha\n",
    "#接着迭代：在同一个数据集中，调整D（分对的，权重降低，分错的，权重提高），再训练得到分类器\\错误率\\alpha\n",
    "#最后得到所有分类器的加权结果:sum(alpha[i]*y[i])\n",
    "def adaBoostTrainDS(dataArr,classLabels,numIt=40):\n",
    "    weakClassArr = [] #记录每次迭代得到的弱分类器[{bestStump1},{bestStump2}...]\n",
    "    m = np.shape(dataArr)[0]\n",
    "    D = np.mat(np.ones((m,1))/m)   #init D to all equal\n",
    "    aggClassEst = np.mat(np.zeros((m,1))) #记录每个样本数据的类别估计累计值(加权累加)\n",
    "    errorRate = 0.0\n",
    "    for i in range(numIt):\n",
    "        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump\n",
    "        #print \"D:\",D.T\n",
    "        #下面公式见P117-118\n",
    "        alpha = float(0.5*np.log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0\n",
    "        bestStump['alpha'] = alpha  \n",
    "        weakClassArr.append(bestStump)                  #store Stump Params in Array\n",
    "        #print \"classEst: \",classEst.T\n",
    "        expon = np.multiply(-1*alpha*np.mat(classLabels).T,classEst) #exponent for D calc, getting messy\n",
    "        D = np.multiply(D,np.exp(expon))                              #Calc New D for next iteration\n",
    "        D = D/D.sum()\n",
    "        #calc training error of all classifiers, if this is 0 quit for loop early (use break)\n",
    "        aggClassEst += alpha*classEst\n",
    "        #print \"aggClassEst: \",aggClassEst.T\n",
    "        #可以通过变量aggClassEst的符号，来判断类别：sign(sum(alpha[i]*y[i]))函数\n",
    "        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T,np.ones((m,1))) \n",
    "        errorRate = aggErrors.sum()/m #分错的样本数\n",
    "        #print \"total error: \",errorRate\n",
    "        if errorRate == 0.0: \n",
    "            break\n",
    "    return weakClassArr,aggClassEst,errorRate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D: [[ 0.2  0.2  0.2  0.2  0.2]]\nclassEst:  [[-1.  1. -1. -1.  1.]]\naggClassEst:  [[-0.69314718  0.69314718 -0.69314718 -0.69314718  0.69314718]]\ntotal error:  0.2\nD: [[ 0.5    0.125  0.125  0.125  0.125]]\nclassEst:  [[ 1.  1. -1. -1. -1.]]\naggClassEst:  [[ 0.27980789  1.66610226 -1.66610226 -1.66610226 -0.27980789]]\ntotal error:  0.2\nD: [[ 0.28571429  0.07142857  0.07142857  0.07142857  0.5       ]]\nclassEst:  [[ 1.  1.  1.  1.  1.]]\naggClassEst:  [[ 1.17568763  2.56198199 -0.77022252 -0.77022252  0.61607184]]\ntotal error:  0.0\n"
     ]
    }
   ],
   "source": [
    "weakClassArr,aggClassEst,errorRate = adaBoostTrainDS(datMat,classLabels,9)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'dim': 0, 'ineq': 'lt', 'thresh': 1.3, 'alpha': 0.6931471805599453}, {'dim': 1, 'ineq': 'lt', 'thresh': 1.0, 'alpha': 0.9729550745276565}, {'dim': 0, 'ineq': 'lt', 'thresh': 0.90000000000000002, 'alpha': 0.8958797346140273}]\n"
     ]
    }
   ],
   "source": [
    "print weakClassArr\n",
    "#可以看出，训练了3个弱分类器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "#adaBoost分类函数\n",
    "#（数据集，训练好的多个分类器）\n",
    "#利用训练好的多个弱分类器，进行加权分类\n",
    "def adaClassify(datToClass,classifierArr):\n",
    "    dataMatrix = np.mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS\n",
    "    m = np.shape(dataMatrix)[0]\n",
    "    aggClassEst = np.mat(np.zeros((m,1))) \n",
    "    for i in range(len(classifierArr)):\n",
    "        classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'],\\\n",
    "                                 classifierArr[i]['thresh'],\\\n",
    "                                 classifierArr[i]['ineq'])#call stump classify\n",
    "        aggClassEst += classifierArr[i]['alpha']*classEst #分类估计值的加权累加和\n",
    "        #print aggClassEst\n",
    "    return np.sign(aggClassEst)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.69314718]\n [-0.69314718]]\n[[ 1.66610226]\n [-1.66610226]]\n[[ 2.56198199]\n [-2.56198199]]\n[[ 1.]\n [-1.]]\n"
     ]
    }
   ],
   "source": [
    "pred = adaClassify([[5,5],[0,0]],weakClassArr)\n",
    "print pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "#用一个难数据集，测试一下\n",
    "\n",
    "def loadDataSet(fileName):      #general function to parse tab -delimited floats\n",
    "    numFeat = len(open(fileName).readline().split('\\t')) #get number of fields \n",
    "    dataMat = []; labelMat = []\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        lineArr =[]\n",
    "        curLine = line.strip().split('\\t')\n",
    "        for i in range(numFeat-1):\n",
    "            lineArr.append(float(curLine[i]))\n",
    "        dataMat.append(lineArr)\n",
    "        labelMat.append(float(curLine[-1]))\n",
    "    return dataMat,labelMat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total error:  0.284280936455\ntotal error:  0.284280936455\ntotal error:  0.247491638796\ntotal error:  0.247491638796\ntotal error:  0.254180602007\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total error:  0.240802675585\ntotal error:  0.240802675585\ntotal error:  0.220735785953\ntotal error:  0.247491638796\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total error:  0.230769230769\n"
     ]
    }
   ],
   "source": [
    "#训练\n",
    "trainArr,trainLabel = loadDataSet('adaBoost/horseColicTraining2.txt')\n",
    "weakClassArr1,aggClassEst1,errorRate1 = adaBoostTrainDS(trainArr,trainLabel,10)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.238805970149\nshould be 16/67 0.238805970149\n"
     ]
    }
   ],
   "source": [
    "#测试\n",
    "testArr,testLabel = loadDataSet('adaBoost/horseColicTest2.txt')\n",
    "pred1 = adaClassify(testArr,weakClassArr1)\n",
    "testError = np.mean(pred1.A.ravel()!=np.array(testLabel))\n",
    "print testError\n",
    "print 'should be 16/67',16.0/67"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at iters  1 train error= 0.284280936455 test error= 0.238805970149\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at iters  10 train error= 0.230769230769 test error= 0.238805970149\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at iters  30 train error= 0.217391304348 test error= 0.238805970149\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at iters  50 train error= 0.1872909699 test error= 0.238805970149\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "at iters  100 train error= 0.190635451505 test error= 0.238805970149\n"
     ]
    }
   ],
   "source": [
    "#来看看分类器的个数的增加，算法的训练和测试效果\n",
    "#这里稍微改了一下adaBoostTrainDS(),最后一行多一个返回errorRate,注释掉一些输出\n",
    "for iters in [1,10,30,50,100]:\n",
    "    weakClassArr,aggClassEst,errorRate = adaBoostTrainDS(trainArr,trainLabel,iters)\n",
    "    pred = adaClassify(testArr,weakClassArr1)\n",
    "    testError = np.mean(pred.A.ravel()!=np.array(testLabel))\n",
    "    print 'at iters ',iters,'train error=',errorRate,'test error=',testError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
